package algorithme;

import model.Arc;
import model.Graph;
import model.Noeud;

import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * User: Thomas
 * Date: 04/02/14
 * Time: 10:49
 */
public class AlgorithmeDijkstra extends AlgorithmePlusCourtChemin {

    /**
     * Recherche le plus court chemin par l'algorithme de Dijkstra
     * @param graph le graph dans lequel se situe la recherche
     * @param source le noeud de départ
     * @param destination le noeud de destination
     * @return la liste chainée de destination vers la source
     */
    @Override
    protected LinkedListNoeudPath plusCourtChemin(Graph graph, Noeud source, Noeud destination) {
        //Initialisation du tableau des distances
        HashMap<Integer, LinkedListNoeudPath> distances = this.initTableauDistance(graph,source);
        PriorityQueue<LinkedListNoeudPath> file_attente = new PriorityQueue<LinkedListNoeudPath>();
        LinkedListNoeudPath u;

        inserer(distances.get(source.getId()),file_attente);

        while(!est_vide(file_attente)) {
            u = noeud_de_distance_minimum(file_attente);
            //supprimer(u,file_attente);

            //Parcours de tous les arcs du graph
            for (Arc arc : u.getValue().getNext()) {

                //LinkedListNoeudPath de destination de l'arc courant
                LinkedListNoeudPath v = distances.get(arc.getDestination().getId());
                //LinkedListNoeudPath de source de l'arc courant

                double d = u.getDistance() + arc.getCout();

                //si la distance est plus courte ou si la distance est égal et qu'il y a moins de correspondance
                if ( d < v.getDistance() /*||
                            (d == v.getDistance() && v.getNbCorrespondance() > sourceLinked.getNbCorrespondance())*/ ) {

                    v.setDistance(d);

                    //on modifie ou on ajoute un prédécesseur
                    v.setPrevious(u);
                    v.setArc(arc);

                    //si l'arc courant est une correspondance on incrémente
                    if (arc.getLigne().equals("0")) {
                        v.setNbCorrespondance(u.getNbCorrespondance() + 1);
                    } else {
                        v.setNbCorrespondance(u.getNbCorrespondance());
                    }

                    mettre_a_jour_ou_inserer(v,file_attente);
                }
            }
        }

        //parcours du chemin trouvé à l'envers, destination -> source
        return distances.get(destination.getId());
    }

    public void inserer(LinkedListNoeudPath node,PriorityQueue<LinkedListNoeudPath> file_attente){
        file_attente.offer(node);
    }

    public boolean est_vide(PriorityQueue<LinkedListNoeudPath> file_attente){
        return file_attente.isEmpty();
    }

    public LinkedListNoeudPath noeud_de_distance_minimum(PriorityQueue<LinkedListNoeudPath> file_attente){
        LinkedListNoeudPath node =file_attente.poll();
        System.out.println("noeud_de_distance_minimum " + node.getValue().getName());
        return node;
    }

    public void supprimer(LinkedListNoeudPath node,PriorityQueue<LinkedListNoeudPath> file_attente){
        file_attente.remove(node);
        System.out.println("supprimer " + node.getValue().getName());
    }

    public void mettre_a_jour_ou_inserer(LinkedListNoeudPath node,PriorityQueue<LinkedListNoeudPath> file_attente){
        file_attente.remove(node);
        file_attente.offer(node);

        System.out.println("mettre_a_jour_ou_inserer " + node.getValue().getName());
    }
}